package oj;

import java.util.LinkedList;
import java.util.Queue;

public class LC117 {
    //层序遍历一个一个连接
//    public Node connect(Node root) {
//        if(root==null) return null;
//        Queue<Node> q=new LinkedList<>();
//        q.offer(root);
//        while(!q.isEmpty()){
//            int size=q.size();
//            Node node=null;
//            for(int i=0;i<size;i++){
//                Node f=q.poll();//如果f为空，说明他是这一行的第一个节点，那么就让node=f，否则让node.next=f;
//                if(node!=null){
//                    node.next=f;
//                }
//                node=f;
//                if(f.left!=null){
//                    q.offer(f.left);
//                }
//                if(f.right!=null){
//                    q.offer(f.right);
//                }
//            }
//        }
//        return root;
//
//    }


    public Node connect(Node root) {
        if(root==null) return root;
        //cur我们把他看作每一层的链表
        Node cur=root;
        while(cur!=null){
            //遍历当前层的时候，为了方便操作下一层，因此加上一个虚拟头结点
            //因为这里是遍历访问这一层，串下一层
            Node dummyHead=new Node(0);
            //prev表示访问到的下一层节点的前一个节点
            Node prev=dummyHead;
            //开始遍历当前层的链表
            while(cur!=null){
                if(cur.left!=null){
                    //如果当前节点的左子节点不为空，就让prev.next指向它
                    prev.next=cur.left;
                    prev=prev.next;
                }
                //与左子树同理
                if(cur.right!=null){
                    prev.next=cur.right;
                    prev=prev.next;
                }
                //继续访问这一行的下一个节点（当前遍历的这一层已经是串好了，是链表）
                cur=cur.next;
            }
            //把下一层串成一个链表后，让它赋值给cur，
            //继续访问下一层，直到cur为空为止。
            cur=dummyHead.next;
        }
        return root;
    }
}
